/* 
 * 周教授讲授计算机算法课程，班上一共有72个学生。每一周，周教授都安排这些学生见一次面。
 * 有些周，周教授将72名学生分为每组8人，另外一些周，周教授将72名学生分为每组9人。
 * 只要两个学生被分在同一组，就算见一次面。周教授分组的原则是，在整个授课过程中，任意两
 * 个学生必须见一次面，且仅见一次面。问，周教授的课程需要安排多少周？周教授需要如何将这
 * 些学生分组？
 * 
 * 周教授有125名学生，将其分为25组，每组5名学生，周教授的课一共上31周。每一周，周教授
 * 让这些学生见一次面。如果算法课程结束时，任意两个学生恰好见了一次面，问，周教授如何分
 * 组？
 */

/*
 *  算法优化：
 *     1）从meeted数组中找一个未见过面的；将两人安排在一组；
 *     2）从将两人加入当前分组，或新建一个分组
 */

#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <set>

#define STUDENT_NUM  72

class Relation
{
private:
    int meeted[STUDENT_NUM][STUDENT_NUM] = {0};

public:
    Relation()
    {
        for (int i = 0; i < STUDENT_NUM; i++) {
            meeted[i][i] = 1;
        }
    }

    void print()
    {
        printf("Meeted:\n");
        for (int i = 0; i < STUDENT_NUM; i++) {
            for (int k = 0; k < STUDENT_NUM; k++)
                printf("%3d", meeted[i][k]);
            printf("\n");
        }
    }

    bool solved()
    {
        for (int i = 0; i < STUDENT_NUM; i++) {
            for (int k = 0; k < STUDENT_NUM; k++)
                if (!meeted[i][k]) {
                    return false;
                }
        }
        return true;
    }

    bool is_meeted(int a, int b)
    {
        return meeted[a][b];
    }

    void meet(int a, int b)
    {
        meeted[a][b] = 1;
        meeted[b][a] = 1;
    }

    void unmeet(int a, int b)
    {
        meeted[a][b] = 0;
        meeted[b][a] = 0;
    }
};

Relation relation;
class Group;
std::vector<Group *> solution;

// 分组类
class Group
{
private:
    int  student_num;   // 学员人数
    std::vector< int >            grouped;   // 学员i是否已经分组
    std::vector< std::set<int> >  groups;    // 学员分组方案

public:
    Group(int num)
    {
        std::cout << "Enter new Group class." << std::endl;
        student_num = num;
        groups.clear();
        grouped.resize(num);
        std::cout << "Exit new Group class." << std::endl;
    }

    void print_group(int id)
    {
        printf("Group[%d]:", id);
        for (auto item = groups[id].begin(); item != groups[id].end(); item++)
            printf("%3d", *item);
        printf("\n");
    }

    void print()
    {
        printf("Groups:\n");
        for (int i = 0; i < groups.size(); i++)
            print_group(i);
    }

    // 查找两个未分组且未见过面的学员
    bool find_unmeeted(int& a, int& b, Relation *relation)
    {
        for (a = 0; a < student_num; a++) {
            for (b = 0; b < student_num; b++) {
                if (!grouped[a] && !grouped[b] && !relation->is_meeted(a, b)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 查找与group分组的成员均未见过面的学员
    int find_unmeeted(std::set<int>& group, Relation *relation)
    {
        for (int i = 0; i < student_num; i++) {
            if (grouped[i]) continue;
            bool found = true;
            for (auto item = group.begin(); item != group.end(); item++) {
                if (relation->is_meeted(*item, i)) found = false;
            }
            if (found) return i;
        }
        return -1;
    }

    void divide(int group_id, Relation relation, int remains)
    {
        // 如果找到解，则输出
        std::cout << "进行新一组的分组..." << std::endl;
        if (remains == 0) {
            // print();
            for (int i = 0; i < solution.size(); i++) {
                printf("第 %d 周:\n", i);
                solution[i]->print();
            }
            relation.print();
            if (relation.solved()) {
                printf("找到解:\n");
                for (int i = 0; i < solution.size(); i++) {
                    printf("第 %d 周:\n", i);
                    solution[i]->print();
                }
                return;
            }

            // 如果还没有找到解，进入下一周的分组
            std::cout << "进入下一周分组..." << std::endl;
            Group *next_group = new Group(student_num);
            solution.push_back(next_group);
            next_group->divide(0, relation, student_num);
            solution.pop_back();
            delete next_group;
            return;
        }

        // 找第一个未见面的两个学员a,b, 将这两个学员加入当前分组
        int a, b;
        std::set<int> group;
        if (!find_unmeeted(a, b, &relation)) {
            printf("本轮分组失败，当前分组情况：\n");
            print();
            // 打印所有未分组的学员
            for (int i = 0; i < student_num; i++)
                if (!grouped[i]) printf("%5d", i);
            printf("\n");
            // 打印相遇的情况
            relation.print();
            return;
        }
        // printf("找到两个未相遇的学员:(%d, %d)\n", a, b);
        group.insert(a);
        group.insert(b);
        grouped[a] = 1;
        grouped[b] = 1;
        relation.meet(a, b);

        // 查找本组学员均未见面的学员，加入本组
        while (group.size() < 9) {
            a = find_unmeeted(group, &relation);
            if (a == -1) {
                // 如找不到与本组成员均未见面的学员，且本组成员数达到8，则进入下一轮
                if (group.size() == 8)
                    break;
                // 回溯时需还原
                for (auto item1 = group.begin(); item1!=group.end(); item1++) {
                    grouped[*item1] = 0;
                    for (auto item2 = group.begin(); item2!=group.end(); item2++)
                        if (*item1 != *item2) relation.unmeet(*item1, *item2);
                }
                return;
            }
            // printf("add new student:(%d)\n", a);
            for (auto item = group.begin(); item != group.end(); item++) {
                relation.meet(a, *item);
            }
            group.insert(a);
            grouped[a] = 1;
        }

        // 将本次分组加入总的分组中
        groups.push_back(group);

        // 进入下一轮
        divide(group_id + 1, relation, remains - group.size());
    }
};

int main()
{
    Relation relation;
    Group *group = new Group(STUDENT_NUM);
    solution.push_back(group);
    group->divide(0, relation, STUDENT_NUM);
    solution.pop_back();
    delete group;
}